/*
https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/submissions/578096269/
902. 最大为N的数字组合
数位DP
*/

class Solution {
    vector<int> ndigits;
    vector<int> checkdigits;
    int size;
    int dp[11][11];
    int dfs(int idx,bool lead,bool limit,int prev){
        if(idx>=size) return 1;
        if(!lead&&!limit&&dp[idx][prev]>=0) return dp[idx][prev];
        int up=(limit)?ndigits[idx]:9;
        int res=0;//需要注意前导0
        if(lead&&(idx!=size-1)&&checkdigits[0]!=0)res=dfs(idx+1,true,false,0);
        for(int i=0;i<checkdigits.size();i++){
            if(checkdigits[i]>up) break;
            res+=dfs(idx+1,lead&&(!checkdigits[i]),limit&&(checkdigits[i]==up),checkdigits[i]);
        }
        if(!lead&&!limit)dp[idx][prev]=res;
        return res;
    }
public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        while(n){
            ndigits.push_back(n%10);
            n/=10;
        }
        reverse(ndigits.begin(),ndigits.end());
        for(string& s:digits){
            checkdigits.push_back(stoi(s));//添加元素
        }
        size=ndigits.size();
        memset(dp,-1,sizeof(dp));
        return dfs(0,true,true,0);
    }
};